This specification relates to data access in distributed systems.
Distributed network-based data storage, for example accessible over the Internet, has various applications. One application is video storage and access.
During the past decade, online video streaming has gained increasing popularity among Internet users as high speed Internet service is now readily available for households. For example, while traditional video delivery systems (e.g., cable television systems) may no longer satisfy customers' growing demand for convenient access and instant delivery, movie consumers may soon turn to online video stores that may provide such service. However, in practice, it is nontrivial to build an Internet-based storage system, equipped with libraries comparable in size to traditional video rental stores, for providing reliable movie download service to consumers at a reasonable cost. The following example illustrates some of the difficulty behind the idea.
Consider a sample system for a movie download service with 20K movie titles each 2 hrs in length encoded at 2.5 Mbps that is configured to serve 15K simultaneous sessions. In the past, this would have been considered an extensive library for a well-equipped video rental store. (In comparison, NetFlix currently lists a growing number of about 70K+ titles.) Since each movie title occupies about 2.25 GB storage (i.e., 2 hr*2.5 Mb/s*60 sec*60 min/8), the amount of raw storage needed for 20K titles is 45 TB. In addition, if mirroring is used for resilience, the minimum storage required for this entire library is 90 TB, which can be achieved by using approximately 96 1 TB disks organized as e.g., 4 servers each having 24 disk drives.
In the above sample system, the amount of access bandwidth needed for allowing 15K simultaneous sessions is 37.5 Gbps, which would then require ˜400 Mbps from each of the 96 disks assuming an equal load over these disks. However, this access rate would exceed common practice for general purpose storage systems. Under typical workloads, a conventional storage system may be able to provide an average bandwidth of 50 Mbps per disk. Even tuned media storage servers that have been configured to supply extraordinary bandwidth of up to about 150˜200 Mbps may no longer be sufficient for the sample system. Moreover, the level of difficulty in achieving satisfactory access bandwidth rises progressively with the size of the sample system.
Some approaches to determining a system configuration for such an application may approach the problem at issue essentially as dynamic distributed real-time resource allocation, which is particularly hard to solve for large systems since the problem usually grows with combinatorial complexity as the system expands in size. Briefly, a dynamic distributed real-time resource allocation and scheduling problem in nature can be characterized as an NP complete problem, which means that there are no deterministic solutions computable within a tractable/practical period of time, in other words, the solutions have combinatorial complexity in space and/or time. Traditional approaches to solving NP complete problems often try to restrict the problem in some manner so that the restricted problem is amenable to a deterministic solution. However, such restricted solutions may fail for a number of reasons. For instance, the solution to the restricted problem may not actually reflect the solution to the original problem. Furthermore, when the deterministic solution hits boundary conditions in the problem space, the problem turns combinatorial again, sometimes causing the deterministic solution to produce catastrophic results.